package cn.zhl.algorithm._1_排序;

/**
 * @program: demos
 * @description: 快速排序，指定一个数，大的右边，小的左边，开始从右往左，遇到比begin小的就掉头
 * 				然后从左往右，遇到比begin大的就掉头
 * @author: 刘振华
 * @create: 2020-06-07 13:26
 **/
public class QuickSort extends Sort{
	@Override
	protected void sort() {
		qsort(0,array.length);
	}
	private void qsort(int begin,int end){
		if(end-begin<2){
			return;
		}
		int mid = findIndex(begin, end);
		qsort(begin,mid);
		qsort(mid+1,end);
	}

	private int findIndex(int begin,int end){
//		System.out.println("first:"+begin+":"+end);
		end--;
		Integer bNum= array[begin];
		while (end>begin){
//			System.out.println("second:"+begin+":"+end);
			//从右向左
			while (end>begin){
				if(array[end]>bNum){
					end--;
				}else{
					array[begin++]=array[end];
					break;
				}
			}
			//从左向右
			while (end>begin){
				if(array[begin]<bNum){
					begin++;
				}else {
					array[end--]=array[begin];
					break;
				}
			}
		}

		array[begin] = bNum;
//		System.out.println("rs:"+begin);
		return begin;
	}

}
